package Z.dailyExercise.April;

import java.util.ArrayList;
import java.util.List;

public class _39组合总和 {
    List<List<Integer>> res = new ArrayList<>();
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<Integer> track = new ArrayList<>();
        int addRes = 0;
        backtrace(candidates,track,target,addRes,0);
        return res;



    }

    /**
     *
     * @param cand
     * @param track 路径
     * @param target
     * @param addRes
     * @param index 表示每一层的选择是从当前index开始 防止重复 函数内部 用i来递归
     *
     */
    public void backtrace(int[] cand,List<Integer> track,int target,int addRes,int index){
        if (addRes > target){
            return;
        }
        if (addRes == target){
            res.add(new ArrayList<>(track));
            return;
        }

        for (int i = index; i < cand.length; i++) {

            addRes += cand[i];
            track.add(cand[i]);

            backtrace(cand,track,target,addRes,i);

            int last = track.remove(track.size()-1);
            addRes -= last;

        }


    }
}
